package com.zhugang.week11;

/**
 * @program algorithms
 * @description: coinChange
 * @author: chanzhugang
 * @create: 2022/09/01 21:25
 */
public class CoinChange {

    /**
     * 322 零钱兑换
     *
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange(int[] coins, int amount) {
        // 背包模型（完全背包）
        // 每种硬币无限个，凑成总金额最少需要多少个硬币：
        // int[i][j] = min(int[i - 1][j], int[i - 1][j - coins[i]] + 1, .... int[i - 1][j - c * coins[i]] + c)
        // 定义状态
        int n = coins.length;
        int[][] dp = new int[n][amount + 1];

        // 初始化
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= amount; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        for (int c = 0; c < amount / coins[0]; c++) {
            dp[0][c * coins[0]] = c;
        }
        // 状态转移方程
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= amount; j++) {
                int k = j / coins[i];
                for (int c = 0; c <= k; c++) {
                    if (dp[i - 1][j - c * coins[i]] != Integer.MAX_VALUE) {
                        dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - c * coins[i]] + c);
                    }
                }
            }
        }
        // 求结果
        if (dp[n - 1][amount] == Integer.MAX_VALUE) {
            return -1;
        }
        return dp[n - 1][amount];
    }
}